package com.hsw.bledemo.review.algorithm;

import java.util.Arrays;

/**
 * @author: HSW
 * @data: 2024/8/27
 * @desc:
 */
public class SortJava {

    public void selectionSort(int[] array) {
        int length = array.length;

        // 最后一个肯定是最大值，不需要比较，也没得比较
        for (int i = 0; i < length - 1; i++) {
            // 最小值索引默认问未排序数组第一位
            int minIndex = i;

            // 遍历未排序的数组，找出最小值索引
            for (int j = i; j < length; j++) {
                // 和上一个最小值比较，如果比它小，就改变minIndex
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }

            // 交换未排序数组第一位和最小值
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }

        System.out.println(Arrays.toString(array));
    }

    public void bubbleSort(int[] array) {
        int length = array.length;

        for (int i = 0; i < length; i++) {
            // 未排序的数组长度随着i的增加而较少，因为最后一位没有对象可比较，所以要-1，不然数组会溢出
            for (int j = 0; j < length - 1 - i; j++) {
                // 相邻的两个进行比较，如果前面的比后面的大就进行交换
                if (array[j] > array[j + 1]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }

    public void insectSort(int[] array) {
        int length = array.length;
        // 因为要和前面的数进行比较，所以起始索引为1
        for (int i = 1; i < length; i++) {
            // 前一个数的索引
            int preIndex = i - 1;
            // 要插入的对象
            int current = array[i];

            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }

        System.out.println(Arrays.toString(array));
    }
}
